Mesh families are extensively used in rendering and geometry processing applications. Progressive meshes are one of the most widely used representations for applications such as level-of-detail rendering, compression and transmission over communication networks. The progressive mesh representation can be viewed as a family of meshes generated from a given input mesh through repeated application of a single operation: the edge collapse. Other applications, such as high-quality fitting, remeshing and resampling typically require additional operations that lead to improved meshes according to certain criteria (such as the regularity of connectivity and/or approximation quality). Among the most commonly encountered additional operations are those known as edge swap, edge split and vertex insertion.
Many of the applications that make use of mesh families also rely on the existence of parameterization mappings between meshes in a family. For example, if the input mesh of the family has some properties (e.g., texture, color, analysis data), such a mapping is needed to transfer these properties to other meshes in the family which may be used as substitutes for the original mesh. Conversely, if certain computations are more readily performed onto a derived mesh (e.g., on a simplified version of the original), then a mapping back to the original mesh is necessary in order to transfer the results from the derived mesh to it. This is the case, for example, in skeletal deformation scenarios in which it is typically less computationally expensive to modify the coarse features represented by a simpler “skeleton mesh”, and then transfer the modifications back to the detailed mesh. The availability of a mapping between a current and an input mesh is also important for robust remeshing and resampling methods, as it circumvents error-prone strategies such as those based on normal shooting.
Meshes often exhibit features such as sharp creases, curvature discontinuities, etc., which are important and need to be preserved throughout digital processing modifications. Both the set of operations applied to such meshes, as well as the parameterizations between them, should ideally respect and enforce these features.
Methods for establishing parameterizations between arbitrary meshes have recently emerged, as evidenced by V. Kraevoy and A. Sheffer, Cross-Parameterization and Compatible Remeshing of 3D Models. Proceedings of SIGGRAPH 04 ACM Transactions on Graphics Vol 23 No. 3,2004, p. 858-865, and by J. Schreiner and A. Asirvatham and E. Praun and H. Hoppe, Inter-Surface Mapping, Proceedings of SIGGRAPH 04 ACM Transactions on Graphics Vol 23 No. 3, 2004, p. 867-874. However, these approaches are not readily applicable to mesh families as they typically involve heavy computations which cannot be dynamically updated as local mesh operations are performed. Unlike in the case of establishing a mapping between un-related meshes, the problem of dynamically tracking and updating a parameterization through a family of meshes is different in that it has the benefit of an existing high-quality initial parameterization (the identity map), however it requires multiple updates as operations are incrementally applied to the input mesh to derive new meshes in the family.
The usefulness of mesh families and, in particular, of mesh hierarchies has been recognized by many authors. Lee et al. (A. Lee and W. Sweldens and P. Schröder and L. Cowsar and D. Dobkin, MAPS: Multiresolution Adaptive Parameterization of Surfaces, Proceedings of SIGGRAPH 98, 1998, p. 95-104) were among the first to describe a method for parameterizing a family of meshes obtained by decimation from a given mesh “MAPS”, and illustrated the resulting parameterization in the context of a remeshing application.
In P. Sander and J. Snyder and S. J. Gortler and H. Hoppe, Texture Mapping Progressive Meshes, Proceedings of SIGGRAPH 01, 2001, p. 409-416, there is described the parameterization of progressive mesh families (i.e., where a mesh updating operator consists of edge collapses only) with applications to texture transfer. In this case, the input mesh is first decomposed into charts, the simplification process follows taking into account the initial charts and the corresponding parameterizations, and lastly the chart parameterizations are optimized in another pass. It should be noted that the resulting parameterization is computed but once, and cannot be dynamically updated if additional edge collapses are performed. In fact, the edge collapse sequence is prescribed by the process of optimizing texture deviation.
There are multiple examples in recent literature that rely on mesh families for various applications. In addition to the ubiquitous progressive mesh representation (see H. Hoppe, Progressive Meshes, Proceedings of SIGGRAPH 96, 1996, p. 99-108), mesh families are useful in remeshing (see V. Surazhsky and P. Alliez and C. Gotsman, Isotropic Remeshing of Surfaces: a Local Parameterization Approach, Proc. of 12th International Meshing Roundtable, 2003, which offers an example in which a more complex set of operations is involved besides the usual edge collapse), resampling (see A. Lee and H. Moreton and H. Hoppe, Displaced Subdivision Surfaces, Proceedings of SIGGRAPH 00, 2000, p. 85-94), adaptive refinement (see V. Volkov and L. Li, Real-time Refinement and Simplification of Adaptive Triangular Meshes, In Proceedings of IEEE Visualization 2003, IEEE Computer Society Press, p. 155-162) and analysis. Note in this regard that finite element analysis relies heavily on local operations for mesh quality improvement for analysis purposes, see for example S. Owen, “A Survey of Unstructured Mesh Generation Technology”, Proceedings 7th International Meshing Roundtable, Dearborn, Mich., October 1998.
Prior to this invention, no fully satisfactory dynamic method existed for establishing a mapping between the original mesh and the mesh(es) derived from it.